{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## 第7章-支持向量机（SVM）-导读\n",
    "&emsp;&emsp;首先回顾一下感知机模型，感知机模型是当数据线性可分时，如何用一个超平面区分两类不同的数据。对于上述情况，支持向量机和感知机是非常相似的，它们的差别只在于决策函数（损失函数）的不同。  \n",
    "&emsp;&emsp;7.1节介绍的就是线性可分的情况，会和感知机比较，当线性可分时，这就是一个最简单的情况，在7.2节会介绍如何处理数据线性不可分的情况。当一个线性模型，对数据的分类效果不好时，但数据可以用一个曲面进行分隔，将数据的输入变量做变换（即输入空间和特征空间不是完全一致的），在7.3节中，可以用核函数的方法。\n",
    "\n",
    "### 线性可分支持向量机与硬间隔最大化\n",
    "假设空间：$w \\cdot x+b=0$  \n",
    "决策函数：$f(x) = \\text{sign}(w^* \\cdot x + b^*)$，输出的类别是$\\{+1,-1\\}$。\n",
    "<br/><center><img style=\"border-radius: 0.3125em;box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);\" src=\"../../../PhaseFour/Note/image/7-1-Support-Vector.png\"><br><div style=\"color:orange; border-bottom: 1px solid #d9d9d9;display: inline-block;color: #000;padding: 2px;\">图7-1 支持向量</div></center>  \n",
    "\n",
    "&emsp;&emsp;如图7-1所示，圆点和$\\times$点为两种不同的类别，在感知机模型中，只要找到一个超平面把这两组数据分开就可以，得到的超平面不是唯一的，在SVM模型中，得到的超平面是唯一的，模型选择的依据就是**硬间隔最大化**，这个是什么意思呢？当选择一个超平面将两组数据分开，在二维问题中，这个超平面是一条直线（如图7-1中的实线），每一个点到该直线都有一个距离，使得每个点到直线的距离都比较大，因此这条直线就是唯一的，所有这些距离中最小的距离的点组成的平面称为**支撑超平面**（如图7-1的虚线），这些点被称为**支持向量**，图中实线为**分离超平面**，两个支撑超平面之间的距离称为**硬间隔**。“硬”表示所有的点不能在支撑超平面中间，**硬间隔最大化**就是支持向量机模型选择的标准。  \n",
    "&emsp;&emsp;如何使得硬间隔最大化？书中讲述了两个概念：函数间隔和几何间隔。假设有一个超平面$w \\cdot x + b =0$，某一个实例为$x^*$，函数间隔为$|w \\cdot x^* + b|$，几何间隔为$\\displaystyle \\frac{|w \\cdot x^* + b|}{\\|w\\|}$。  \n",
    "&emsp;&emsp;书中描述要使得硬间隔最大化，使用几何间隔，而不用函数间隔。一个点到不同超平面的距离，不能用函数间隔表示。  \n",
    "$\\because |w \\cdot x + b|$可以转换为$y_i(w \\cdot x_i + b)$  \n",
    "$\\therefore$ 几何间隔可以转化为$\\displaystyle \\frac{y_i(w \\cdot x_i + b)}{\\|w\\|}$  \n",
    "$\\because $ 硬间隔最大化表示点到超平面距离最小的点的距离最大  \n",
    "$\\therefore $ **硬间隔最大化公式**为$$\\displaystyle \\max_{w,b} \\min_i \\frac{y_i(w \\cdot x_i + b)}{\\|w\\|}$$  \n",
    "将$\\displaystyle \\frac{1}{\\|w\\|}$提取出来，变为$$\\max_{w,b} \\frac{1}{\\|w\\|} \\min_i y_i(w \\cdot x_i + b) $$  \n",
    "令$y_i(w \\cdot x_i + b) \\geqslant 1$，可以转化为$$\\begin{array}{ll}\n",
    "\\displaystyle \\max_{w,b} & \\displaystyle \\frac{1}{\\|w\\|}\\\\ \n",
    "\\text { s.t. } & y_i(w \\cdot x_i + b) \\geqslant 1\n",
    "\\end{array}$$  \n",
    "$\\because $ 最大化$\\displaystyle \\frac{1}{\\|w\\|}$和最小化$\\displaystyle \\frac{1}{2} \\|w\\|^2$是等价的  \n",
    "最后线性可分的支持向量机的最优化问题为$$\\begin{array}{ll}\n",
    "\\displaystyle \\min_{w,b} & \\displaystyle \\frac{1}{2} \\|w\\|^2 \\\\ \n",
    "\\text { s.t. } & y_i(w \\cdot x_i + b) - 1 \\geqslant 0\n",
    "\\end{array}$$  \n",
    "\n",
    "对偶问题：$$\\begin{array}{ll}\n",
    "\\displaystyle {\\min_\\alpha} & {\\displaystyle \\frac{1}{2}\\sum_{i=1}^N \\sum_{j=1}^N \\alpha_i \\alpha_j y_i y_j (x_i \\cdot x_j) - \\sum_{i=1}^N \\alpha_i} \\\\\n",
    "\\text { s.t. } & {\\displaystyle \\sum_{i=1}^N \\alpha_i y_i = 0} \\\\\n",
    "& {\\alpha_i \\geqslant 0,\\quad i = 1,2, \\cdots, N}\n",
    "\\end{array}$$  \n",
    "最优解：$$w^*=\\sum_{i=1}^N \\alpha_i^* y_i x_i \\\\ b^* = y_j - \\sum_{i=1}^N \\alpha_i^* y_i(x_i \\cdot x_j)$$  \n",
    "\n",
    "### 线性支持向量机与软间隔最大化\n",
    "#### 支持向量\n",
    "最优化问题：  \n",
    "$$\n",
    "\\begin{array}{ll}\n",
    "{\\displaystyle \\min _{w, b, \\xi}} & {\\displaystyle \\frac{1}{2}\\|w\\|^{2}+C \\sum_{i=1}^{N} \\xi_{i}} \\\\ \n",
    "\\text { s.t. } & {y_{i}\\left(w \\cdot x_{i}+b\\right) \\geqslant 1-\\xi_{i}, \\quad i=1,2, \\cdots, N} \\\\ \n",
    "& {\\xi_{i} \\geqslant 0, \\quad i=1,2, \\cdots, N}\n",
    "\\end{array}$$\n",
    "<br/><center><img style=\"border-radius: 0.3125em;box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);\" src=\"../../../PhaseFour/Note/image/7-2-Soft-Margin-Support-Vector.png\"><br><div style=\"color:orange; border-bottom: 1px solid #d9d9d9;display: inline-block;color: #000;padding: 2px;\">图7-2 软间隔的支持向量</div></center>  \n",
    "\n",
    "&emsp;&emsp;软间隔最大化就是允许数据点出现在两个支撑超平面之间（如图7-2），加入了惩罚项，对误分类点进行惩罚，公式中$\\displaystyle \\frac{1}{2}\\|w\\|^2$表示两个支撑超平面之间的几何间隔尽可能大，会纳入更多的数据点，其中也会有误分类的数据点，数据点越多，惩罚$\\displaystyle C \\sum_{i=1}^{N} \\xi_{i}$就越大，$C$为了衡量支撑超平面之间的间隔。当$C$取$\\infty$时，该问题与7.1节的问题是一样的。\n",
    "\n",
    "#### 合页损失函数\n",
    "最优化问题：$$\n",
    "\\sum_{i=1}^{N}\\left[1-y_{i}\\left(w \\cdot x_{i}+b\\right)\\right]_{+}+\\lambda\\|w\\|^{2}\n",
    "$$  \n",
    "<br/><center><img style=\"border-radius: 0.3125em;box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);\" src=\"../../../PhaseFour/Note/image/7-3-Hinge-Loss-Function.png\"><br><div style=\"color:orange; border-bottom: 1px solid #d9d9d9;display: inline-block;color: #000;padding: 2px;\">图7-3 合页损失函数</div></center>  \n",
    "\n",
    "&emsp;&emsp;图7-3中，横轴表示函数间隔，函数间隔$ > 1- \\xi_i$，$\\xi_i$表示为惩罚，$\\xi_i \\geqslant 0$，当函数间隔$ \\geqslant 1$时，$\\xi_i = 0$（即没有惩罚），当函数间隔$ < 1$，$\\xi = 1 - g(w \\cdot x + b)$，在图中表示为实线，其函数为$[1 - y_i(w \\cdot x_i + b)]_+$  \n",
    "对偶问题：  \n",
    "$$\n",
    "\\begin{array}{ll}\n",
    "{\\displaystyle \\min _{\\alpha}} & {\\displaystyle \\frac{1}{2} \\sum_{i=1}^N \\sum_{j=1}^N \\alpha_i \\alpha_j y_i y_j (x_i \\cdot x_j )-\\sum_{i=1}^N \\alpha_i} \\\\ \n",
    "{\\text { s.t. }} & {\\displaystyle \\sum_{i=1}^N \\alpha_i y_i=0} \\\\ \n",
    "{} & {0 \\leqslant \\alpha_i \\leqslant C, \\quad i=1,2, \\cdots, N}\n",
    "\\end{array}\n",
    "$$  \n",
    "参数的最优解：\n",
    "$$w^*=\\sum_{i=1}^N \\alpha_i^* y_i x_i \\\\ \n",
    "b^*=y_j-\\sum_{i=1}^N y_i \\alpha_i^*(x_i \\cdot x_j)$$  \n",
    "\n",
    "### 非线性支持向量机与核函数\n",
    "<br/><center><img style=\"border-radius: 0.3125em;box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);\" src=\"../../../PhaseFour/Note/image/7-4-Nonlinear-Classification-Problems-and-Examples-of-Kernel-Skill.png\"><br><div style=\"color:orange; border-bottom: 1px solid #d9d9d9;display: inline-block;color: #000;padding: 2px;\">图7-4 非线性分类问题与核技巧示例</div></center>\n",
    "\n",
    "&emsp;&emsp;7-4左图中，$x^{(1)}$和$x^{(2)}$是二维输入变量，分为$\\bullet$点和$\\times$点两类，没有办法用一条直线很好的分隔数据，从图中可以看到，$\\times$点离原点近，$\\bullet$点离原点远，将坐标进行变换$z=\\phi(x),\\phi(x)=x^2$，故$z^{(1)}={(x^{(1)})}^2, z^{(2)}={(x^{(2)})}^2$，最后可以得到7-4右图。可见右图是线性可分的，可以用超平面进行分隔，用新的$z$进行支持向量机，因为在支持向量机的对偶形式中出现的是内积形式，现在得到的内积为$k(x_i,x_j)=\\phi(x_i) \\cdot \\phi(x_j)$。  \n",
    "对偶问题：$$\n",
    "\\begin{array}{ll}\n",
    "{\\displaystyle \\min _{\\alpha}} & {\\displaystyle \\frac{1}{2} \\sum_{i=1}^N \\sum_{j=1}^N \\alpha_i \\alpha_j y_i y_j K(x_i, x_j)-\\sum_{i=1}^N \\alpha_i} \\\\ \n",
    "{\\text { s.t. }} & {\\displaystyle \\sum_{i=1}^N \\alpha_i y_i=0} \\\\ \n",
    "{} & {0 \\leqslant \\alpha_i \\leqslant C, \\quad i=1,2, \\cdots, N}\n",
    "\\end{array}\n",
    "$$\n",
    "决策函数：$$\n",
    "f(x)=\\operatorname{sign}\\left(\\sum_{i=1}^N \\alpha_i^* y_i K(x \\cdot x_i)+b^{*}\\right)\n",
    "$$\n",
    "原始形式的最优化问题：$$\\begin{array}{ll} \n",
    "\\min & \\displaystyle \\frac{1}{2}\\|w\\|^2 + C \\sum_i \\xi \\\\\n",
    "\\text{ s.t. } & y_i [w \\cdot \\phi(x)] \\geqslant 1 - \\xi_i \\\\\n",
    "& \\xi_i \\geqslant 0\n",
    "\\end{array}$$  \n",
    "分离超平面为$w \\cdot \\phi(x) + b = 0$  \n",
    "**缺点：** 不知道用什么样的曲面能更好地分隔数据，选择核函数，并没有很强的依据，只能依靠经验去试验，也就是说用核函数技巧，可以解决曲面分类的一些问题，但同时用什么样的曲面去解决，这也是一个新的问题。  \n",
    "\n",
    "### 序列最小最优化算法\n",
    "对偶问题：$$\n",
    "\\begin{array}{ll}\n",
    "{\\displaystyle \\min _{\\alpha}} & {\\displaystyle \\frac{1}{2} \\sum_{i=1}^N \\sum_{j=1}^N \\alpha_i \\alpha_j y_i y_j K(x_i, x_j)-\\sum_{i=1}^N \\alpha_i} \\\\ \n",
    "{\\text { s.t. }} & {\\displaystyle \\sum_{i=1}^N \\alpha_i y_i=0} \\\\ \n",
    "{} & {0 \\leqslant \\alpha_i \\leqslant C, \\quad i=1,2, \\cdots, N}\n",
    "\\end{array}\n",
    "$$  \n",
    "&emsp;&emsp;需要优化的变量是$\\alpha_i$有$N$个，当数据量很大的时候，需要优化的变量非常多，很难计算，所以不优化所有的变量，每一次优化其中的一部分变量。在该算法中，每次优化两个变量。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.2"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
